#include <iostream>
#include <vector>
using namespace std;

class Solution {
	int max_profit(vector<int> &prices, vector<pair<int, int>> &dp)
	{
		int n = prices.size();
		dp[0].first = -prices[0];
		dp[0].second = 0;

		for (int i = 1; i < n; i++) {
			dp[i].first = max(dp[i - 1].first, -prices[i]);
			dp[i].second = max(dp[i - 1].second, dp[i - 1].first + prices[i]);
		}
		return dp[n - 1].second;
	}

        int max_profit(vector<int> &prices)
        {
                int min_profit = prices[0];
                int ans = 0;
                for(int i = 1; i < prices.size(); i++){
                        min_profit = min(min_profit, prices[i]);
                        ans = max(ans, prices[i] - min_profit);
                }
                return ans;
        }

    public:
	int maxProfit(vector<int> &prices)
	{
		//vector<pair<int, int>> dp(prices.size(), make_pair(0, 0));
		return max_profit(prices);
	}
};

int main()
{
	vector<int> prices{ 7, 1, 5, 3, 6, 4 };
	cout << Solution().maxProfit(prices) << endl;
	return 0;
}